package com.example.algorithm.dynamicprogramming;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * 给定一个三角形 triangle ，找出自顶向下的最小路径和。
 *  每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。
 *  也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
 *
 *  示例 1：
 * 输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
 * 输出：11
 * 解释：如下面简图所示：
 *    2
 *   3 4
 *  6 5 7
 * 4 1 8 3
 * 自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
 *
 *  示例 2：
 * 输入：triangle = [[-10]]
 * 输出：-10
 */
public class Leetcode120_MinimumTotal {
    static class Solution {
        /**
         * 动态规划
         * 和 LeetCode64类似
         * 要到达(i, j) 必须先到(i - 1, j - 1)或者(i - 1, j)
         * dp[i][j]表示从起点跳到(i, j)的最小路径和
         * 则 dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1]) + triangle[i][j]
         * @param triangle
         * @return
         */
        public int minimumTotal(List<List<Integer>> triangle) {
            int n = triangle.size();
            int[][] dp = new int[n][n]; // dp[i] = m 表示从起点(0, 0)跳到(i, j)的最小路径和为 m
            dp[0][0] = triangle.get(0).get(0); // 初始化
            for (int i = 1; i < n; i++) {
                for (int j = 0; j < i + 1; j++) {
                    if (j > 0 && j < i)
                        dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j - 1]) + triangle.get(i).get(j);
                    else if (j == 0) // 边界值处理1：每行的第一个只能通过上一行的第一个才能跳到
                        dp[i][j] = dp[i - 1][0] + triangle.get(i).get(j);
                    else  // 边界值处理2：每行的最后一个只能通过上一行的最后一个才能跳到
                        dp[i][j] = dp[i - 1][j - 1] + triangle.get(i).get(j);
                }
            }
            return Arrays.stream(dp[n - 1]).min().getAsInt();
        }
    }

    public static void main(String[] args) {
        List<List<Integer>> triangle =  new ArrayList<>();
        triangle.add(Collections.singletonList(2));
        triangle.add(Arrays.asList(3, 4));
        triangle.add(Arrays.asList(6, 5, 7));
        triangle.add(Arrays.asList(4, 1, 8, 3));
        System.out.println(new Solution().minimumTotal(triangle));
    }
}
